1. Field of the Invention
The said invention is applied to searching for a shortest path (with constraints) from a single source node to a single destination node in a flat computer network. The shortest path search function which implements this new method is used by the routing module running in a router of a packet (or cell) switching network or running in a switching node of a circuit switching network.
2. Description of the Related Art
A flat computer network (or each flat layer of a hierarchical network) consists of multiple number of nodes (i.e. dedicated purpose computers) connected by communication links, and forms a certain two dimensional topology. Each communication link is assigned a cost which is determined by considerations of application requirements [1]. When a packet (or cell) is to be sent or a circuit is to be built from a source node to a destination node in a network, it is required to find a shortest path among all available paths between the source and the destination. If all links in a network are assigned the same cost, the shortest path is a minimum hop path. If link costs are different, the shortest path is a minimum cost path. In the latter case the number of hops in a minimum cost path may exceed that in a minimum hop path.
The most popular method used by the current art to search for a shortest path is Dijkstra algorithm which may be a classic Dijkstra algorithm or an improved version of Dijkstra algorithm. Dijkstra algorithm has been described in many literatures [1] [3], and may be applied in two different cases.                1. To find shortest paths from a single source node to all other nodes in a network. Dijkstra algorithm makes a flood search and builds a shortest path tree with the source node as its root, and with all other nodes in the network as branch nodes or leave nodes of the tree. The search will terminate when all nodes in the network are linked up to the tree. The time complexity of Dijkstra algorithm in case 1 is O(PN2) where PN is the total number of nodes in the network [4]. Dijkstra algorithm is efficient enough when applied in this case.        2. To find a shortest path from a single source node to a single destination node in a network. Dijkstra algorithm works in the same way as it does in case 1, but the search will terminate when the destination node is attached to the tree [2]. In this case Dijkstra algorithm also builds a shortest path tree with the source node as its root and a subset of the nodes in the network as branch nodes or leave nodes of the tree. The destination node is the last leave node being attached to the tree. In the case of searching for a minimum hop path this algorithm creates a minimum hop path tree. In the worst luck case it has to find all the minimum hop paths to all the nodes which are as far away as or less far away than the destination node from the source node (i.e. all the nodes lying in the searching range shown by the big circle in drawing sheet 1-1), even though it is only required to find one path to a single destination node. In the case of searching for a minimum cost path this algorithm builds a minimum cost path tree. In the worst luck case it has to find all the minimum cost paths from the source to all the nodes which are at the same cost away as or less cost away than the destination node from the source node (i.e. all the nodes lying in the big searching range circle shown by drawing sheet 1-1). In other words the problem of finding a shortest path (minimum hop or minimum cost path) from a single source to a single destination by Dijkstra algorithm is equivalent to the problem of finding all shortest paths from a single source node to all the nodes in a sub-network lying within the boundary of the big circle in sheet 1-1. The center of the big circle is the source node and the radius is the number of hops or the cost of the path from the source to the destination. Bear in mind that sheet 1-1 is a topology map rather than a geographic map. All hops or all equal cost paths are displayed by equal length straight lines, although they are not equal in length geographically. Hence, all nodes which are at the same hops away or at the same path cost away from the source node lie on the circumference of a circle. The time complexity of Dijkstra algorithm in case 2 is O(PD2) where PD is the total number of nodes in the sub-network which includes all nodes in the big circle shown by sheet 1-1 [4].        
Obviously Dijkstra algorithm is not efficient enough in case 2, as it has to find a large number of shortest paths which are not required while the purpose is to find only one shortest path from a single source to a single destination.
In a large high speed network the set up time of a shortest path from a single source to a single destination is a very important parameter, especially from the point of view of path switching on failure or preemption. The rerouting of a lot of connections that were using a failing or preempted link or node may lead to a high number of simultaneous new path set up and create a burst of processing overhead. In order to avoid disrupting the connections at the end user level in the above situation it is highly desirable to reduce both the overhead of a shortest path search algorithm and the shortest path set up time.